// 给定一个二叉树，将其进行左右翻转

// 思路1：后序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小
function invertTree(root) {
    if (!root) {
        return null
    }
    let left = invertTree(root.left)
    let right = invertTree(root.right)
    root.left = right
    root.right = left
    return root
}

// 思路2：迭代法,后序

function invertTree2(root) {
    if (!root) {
        return root
    }
    let stack = [root]
    while (stack.length) {
        let node = stack.pop()
        if (!node) {
            let curNode = stack.pop()
            let leftNode = curNode.left
            let rightNode = curNode.right
            curNode.right = leftNode
            curNode.left = rightNode
            continue
        }
        if (node.right) {
            stack.push(node.right)
        }
        if (node.left) {
            stack.push(node.left)
        }
        stack.push(node)
        stack.push(null)
    }
    return root
}

// 思路3：层序遍历

function invertTree3(root) {
    if (!root) {
        return root
    }
    let queue = [root]
    while (queue.length) {
        let len = queue.length
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            let leftNode = node.left
            let rightNode = node.right
            node.right = leftNode
            node.left = rightNode
            if (node.left) {
                queue.push(node.left)
            }            
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return root
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};

console.log(invertTree3(root))